package three_shang.智能算法;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class TabuSearch {
    private static final int NUM_CITIES = 4;
    private static final double[][] DISTANCES = {
            {0, 1, 0.5, 1},
            {1, 0, 1, 1},
            {1.5, 5, 0, 1},
            {1, 1, 1, 0}
    };
    private static final int TABU_TENURE = 3;
    private static final int MAX_ITERATIONS = 100;

    public static void main(String[] args) {
        // 初始化路径 (a, b, c, d)
        List<Integer> currentSolution = Arrays.asList(0, 1, 2, 3, 0);
        List<Integer> bestSolution = new ArrayList<>(currentSolution);
        double bestCost = calculateCost(bestSolution);

        // 初始化禁忌列表
        int[][] tabuList = new int[NUM_CITIES][NUM_CITIES];
        // 禁忌搜索算法
        for (int iteration = 0; iteration < MAX_ITERATIONS; iteration++) {
            List<Integer> bestNeighbor = null;
            double bestNeighborCost = Double.MAX_VALUE;

            // 生成邻域 (交换两个城市)
            for (int i = 1; i < NUM_CITIES; i++) {
                for (int j = i + 1; j < NUM_CITIES; j++) {
                    List<Integer> neighbor = new ArrayList<>(currentSolution);
                    // 交换城市位置
                    swap(neighbor, i, j);

                    double cost = calculateCost(neighbor);

                    // 检查禁忌条件
                    if ((tabuList[i][j] == 0 || cost < bestCost) && cost < bestNeighborCost) {
                        bestNeighbor = neighbor;
                        bestNeighborCost = cost;
                    }
                }
            }

            // 更新当前解
            currentSolution = new ArrayList<>(bestNeighbor);

            // 更新禁忌列表
            for (int i = 0; i < NUM_CITIES; i++) {
                for (int j = 0; j < NUM_CITIES; j++) {
                    if (tabuList[i][j] > 0) {
                        tabuList[i][j]--;
                    }
                }
            }

            // 将本次选择的交换操作加入禁忌列表
            //对交换过的位置 '冷却'
            int swappedCity1 = findSwapIndex(bestSolution, currentSolution);
            int swappedCity2 = findSwapIndex(currentSolution, bestSolution);
            if (swappedCity1 != -1 && swappedCity2 != -1) {            // 检查是否找到了有效的交换索引
                tabuList[swappedCity1][swappedCity2] = TABU_TENURE;
                tabuList[swappedCity2][swappedCity1] = TABU_TENURE;
            }

            // 更新最优解
            if (bestNeighborCost < bestCost) {
                bestCost = bestNeighborCost;
                bestSolution = new ArrayList<>(currentSolution);
            }

            System.out.println("迭代次数 " + iteration + "    当前最短距离= " + bestCost);
        }

        System.out.println("最短路径: " + bestSolution);
        System.out.println("最短距离: " + bestCost);
    }

    private static double calculateCost(List<Integer> solution) {
        double cost = 0;
        for (int i = 0; i < solution.size() - 1; i++) {
            cost += DISTANCES[solution.get(i)][solution.get(i + 1)];
        }
        return cost;
    }

    private static void swap(List<Integer> solution, int i, int j) {
        int temp = solution.get(i);
        solution.set(i, solution.get(j));
        solution.set(j, temp);
    }

    private static int findSwapIndex(List<Integer> original, List<Integer> modified) {
        for (int i = 0; i < original.size(); i++) {
            if (!original.get(i).equals(modified.get(i))) {
                return i;
            }
        }
        return -1; // 未找到不同之处
    }
}
